package com.fengye.algorithms.leecode.dp;

/**
 * @author loupf50246
 * @date 2023/7/9 18:49
 */
public class FindTargetSumWays494 {
    public static void main(String[] args) {
        int[] nums = {1, 1, 1,1,1};
        System.out.println(findTargetSumWays1(nums, 3));
    }

    public static int findTargetSumWays(int[] nums, int target) {
        int length = nums.length;
        // 数组求和
        int sum = 0;
        for (int  num : nums) {
            sum += num;
        }

        // 如果所有数据的和小于target,或者sum - target是奇数
        // 说明无论怎么添加符号，表达式的值都不可能是target
        if (sum < target || ((sum-target) & 1) != 0) {
            return 0;
        }

        // 只要找到一些方案，让元素的和等于capacity
        int capacity = (sum - target) >> 1;

        int[] dp = new int[capacity+1];

        dp[0] = 1;

        for (int i=1; i <= length; i++) {
            for (int j=capacity; j >= 0; j--) {
                if (j >= nums[i-1]) {
                    dp[j] += dp[j - nums[i-1]];
                }
            }
        }

        return dp[capacity];
    }

    public static int findTargetSumWays1(int[] nums, int target) {
        int length = nums.length;

        // 数组求和
        int sum = 0;
        for (int  num : nums) {
            sum += num;
        }

        // 如果所有数据的和小于target,或者sum - target是奇数
        // 说明无论怎么添加符号，表达式的值都不可能是target
        if (sum < target || ((sum-target) & 1) != 0) {
            return 0;
        }

        // 只要找到一些方案，让元素的和等于capacity
        int capacity = (sum - target) >> 1;

        // dp[i][j] 表示在数组nums的前i元素中选择一些元素
        // 使得选择的元素之和等于j的方案数
        int[][] dp = new int[length+1][capacity+1];

        // 边界条件
        dp[0][0] = 1;

        for (int i=1; i<= length; i++) {
            for (int j=0; j <= capacity; j++) {
                if (j >= nums[i-1]) {
                    // 不选第i个和选第i个元素
                    dp[i][j] = dp[i-1][j] + dp[i-1][j - nums[i-1]];
                } else {
                    // 不能选第i个
                    dp[i][j] = dp[i-1][j];
                }
            }
        }

        // 从数组前length个（也就是全部元素）中选择一些元素，让他们的和
        // 等于capacity的方案数
        return dp[length][capacity];
    }
}
